package org.example.leetcode.interview.binarysearch;

public class LC0069 {
    /**
     * 二分法变体, 左右值固定, 需要计算mid并且逐步逼近右值x, mid的平方可以与右值相等
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        int left = 0, right = x, ans = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid + 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        LC0069 solu = new LC0069();
        System.out.println(solu.mySqrt(4));
        System.out.println(solu.mySqrt(8));
    }
}
